// Copyright 2024 Tvux
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package _238

// productExceptSelf
// 超时
// O(n^2)
//func productExceptSelf(nums []int) []int {
//	res := make([]int, len(nums))
//	for i := 0; i < len(nums); i++ {
//		product := 1
//		for j := 0; j < len(nums); j++ {
//			if j != i {
//				product *= nums[j]
//			}
//		}
//		res[i] = product
//	}
//	return res
//}

// productExceptSelf
// 除自身之外的数组乘积 = 数组中这个数左边的乘积 * 数组中这个数右边的乘积
func productExceptSelf(nums []int) []int {
	left := make([]int, len(nums))
	left[0] = 1
	for i := 1; i < len(nums); i++ {
		left[i] = left[i-1] * nums[i-1]
	}

	right := make([]int, len(nums))
	right[len(nums)-1] = 1
	for i := len(nums) - 2; i >= 0; i-- {
		right[i] = right[i+1] * nums[i+1]
	}

	res := make([]int, len(nums))
	for i := 0; i < len(nums); i++ {
		res[i] = left[i] * right[i]
	}
	return res
}
